<!DOCTYPE html>

<html>
  <head>
    <meta charset="utf-8">
    
    <title>numpy.einsum_path &mdash; NumPy v1.18 Manual</title>
    
    <link rel="stylesheet" type="text/css" href="../../_static/css/spc-bootstrap.css">
    <link rel="stylesheet" type="text/css" href="../../_static/css/spc-extend.css">
    <link rel="stylesheet" href="../../_static/scipy.css" type="text/css" >
    <link rel="stylesheet" href="../../_static/pygments.css" type="text/css" >
    <link rel="stylesheet" href="../../_static/graphviz.css" type="text/css" >
    
    <script type="text/javascript">
      var DOCUMENTATION_OPTIONS = {
        URL_ROOT:    '../../',
        VERSION:     '1.18.1',
        COLLAPSE_INDEX: false,
        FILE_SUFFIX: '.html',
        HAS_SOURCE:  false
      };
    </script>
    <script type="text/javascript" src="../../_static/jquery.js"></script>
    <script type="text/javascript" src="../../_static/underscore.js"></script>
    <script type="text/javascript" src="../../_static/doctools.js"></script>
    <script type="text/javascript" src="../../_static/language_data.js"></script>
    <script type="text/javascript" src="../../_static/js/copybutton.js"></script>
    <link rel="author" title="About these documents" href="../../about.html" >
    <link rel="index" title="Index" href="../../genindex.html" >
    <link rel="search" title="Search" href="../../search.html" >
    <link rel="top" title="NumPy v1.18 Manual" href="../../index.html" >
    <link rel="up" title="Linear algebra (numpy.linalg)" href="../routines.linalg.html" >
    <link rel="next" title="numpy.linalg.matrix_power" href="numpy.linalg.matrix_power.html" >
    <link rel="prev" title="numpy.einsum" href="numpy.einsum.html" > 
  </head>
  <body>
<div class="container">
  <div class="top-scipy-org-logo-header" style="background-color: #a2bae8;">
    <a href="../../index.html">
      <img border=0 alt="NumPy" src="../../_static/numpy_logo.png"></a>
    </div>
  </div>
</div>


    <div class="container">
      <div class="main">
        
	<div class="row-fluid">
	  <div class="span12">
	    <div class="spc-navbar">
              
    <ul class="nav nav-pills pull-left">
        <li class="active"><a href="https://numpy.org/">NumPy.org</a></li>
        <li class="active"><a href="https://numpy.org/doc">Docs</a></li>
        
        <li class="active"><a href="../../index.html">NumPy v1.18 Manual</a></li>
        

          <li class="active"><a href="../index.html" >NumPy Reference</a></li>
          <li class="active"><a href="../routines.html" >Routines</a></li>
          <li class="active"><a href="../routines.linalg.html" accesskey="U">Linear algebra (<code class="xref py py-mod docutils literal notranslate"><span class="pre">numpy.linalg</span></code>)</a></li> 
    </ul>
              
              
    <ul class="nav nav-pills pull-right">
      <li class="active">
        <a href="../../genindex.html" title="General Index"
           accesskey="I">index</a>
      </li>
      <li class="active">
        <a href="numpy.linalg.matrix_power.html" title="numpy.linalg.matrix_power"
           accesskey="N">next</a>
      </li>
      <li class="active">
        <a href="numpy.einsum.html" title="numpy.einsum"
           accesskey="P">previous</a>
      </li>
    </ul>
              
	    </div>
	  </div>
	</div>
        

	<div class="row-fluid">
      <div class="spc-rightsidebar span3">
        <div class="sphinxsidebarwrapper">
  <h4>Previous topic</h4>
  <p class="topless"><a href="numpy.einsum.html"
                        title="previous chapter">numpy.einsum</a></p>
  <h4>Next topic</h4>
  <p class="topless"><a href="numpy.linalg.matrix_power.html"
                        title="next chapter">numpy.linalg.matrix_power</a></p>
<div id="searchbox" style="display: none" role="search">
  <h4>Quick search</h4>
    <div>
    <form class="search" action="../../search.html" method="get">
      <input type="text" style="width: inherit;" name="q" />
      <input type="submit" value="search" />
      <input type="hidden" name="check_keywords" value="yes" />
      <input type="hidden" name="area" value="default" />
    </form>
    </div>
</div>
<script type="text/javascript">$('#searchbox').show(0);</script>
        </div>
      </div>
          <div class="span9">
            
        <div class="bodywrapper">
          <div class="body" id="spc-section-body">
            
  <div class="section" id="numpy-einsum-path">
<h1>numpy.einsum_path<a class="headerlink" href="#numpy-einsum-path" title="Permalink to this headline">¶</a></h1>
<dl class="function">
<dt id="numpy.einsum_path">
<code class="sig-prename descclassname">numpy.</code><code class="sig-name descname">einsum_path</code><span class="sig-paren">(</span><em class="sig-param">subscripts</em>, <em class="sig-param">*operands</em>, <em class="sig-param">optimize='greedy'</em><span class="sig-paren">)</span><a class="reference external" href="https://github.com/numpy/numpy/blob/v1.18.1/numpy/core/einsumfunc.py#L704-L992"><span class="viewcode-link">[source]</span></a><a class="headerlink" href="#numpy.einsum_path" title="Permalink to this definition">¶</a></dt>
<dd><p>Evaluates the lowest cost contraction order for an einsum expression by
considering the creation of intermediate arrays.</p>
<dl class="field-list">
<dt class="field-odd">Parameters</dt>
<dd class="field-odd"><dl>
<dt><strong>subscripts</strong><span class="classifier">str</span></dt><dd><p>Specifies the subscripts for summation.</p>
</dd>
<dt><strong>*operands</strong><span class="classifier">list of array_like</span></dt><dd><p>These are the arrays for the operation.</p>
</dd>
<dt><strong>optimize</strong><span class="classifier">{bool, list, tuple, ‘greedy’, ‘optimal’}</span></dt><dd><p>Choose the type of path. If a tuple is provided, the second argument is
assumed to be the maximum intermediate size created. If only a single
argument is provided the largest input or output array size is used
as a maximum intermediate size.</p>
<ul class="simple">
<li><p>if a list is given that starts with <code class="docutils literal notranslate"><span class="pre">einsum_path</span></code>, uses this as the
contraction path</p></li>
<li><p>if False no optimization is taken</p></li>
<li><p>if True defaults to the ‘greedy’ algorithm</p></li>
<li><p>‘optimal’ An algorithm that combinatorially explores all possible
ways of contracting the listed tensors and choosest the least costly
path. Scales exponentially with the number of terms in the
contraction.</p></li>
<li><p>‘greedy’ An algorithm that chooses the best pair contraction
at each step. Effectively, this algorithm searches the largest inner,
Hadamard, and then outer products at each step. Scales cubically with
the number of terms in the contraction. Equivalent to the ‘optimal’
path for most contractions.</p></li>
</ul>
<p>Default is ‘greedy’.</p>
</dd>
</dl>
</dd>
<dt class="field-even">Returns</dt>
<dd class="field-even"><dl class="simple">
<dt><strong>path</strong><span class="classifier">list of tuples</span></dt><dd><p>A list representation of the einsum path.</p>
</dd>
<dt><strong>string_repr</strong><span class="classifier">str</span></dt><dd><p>A printable representation of the einsum path.</p>
</dd>
</dl>
</dd>
</dl>
<div class="admonition seealso">
<p class="admonition-title">See also</p>
<p><a class="reference internal" href="numpy.einsum.html#numpy.einsum" title="numpy.einsum"><code class="xref py py-obj docutils literal notranslate"><span class="pre">einsum</span></code></a>, <a class="reference internal" href="numpy.linalg.multi_dot.html#numpy.linalg.multi_dot" title="numpy.linalg.multi_dot"><code class="xref py py-obj docutils literal notranslate"><span class="pre">linalg.multi_dot</span></code></a></p>
</div>
<p class="rubric">Notes</p>
<p>The resulting path indicates which terms of the input contraction should be
contracted first, the result of this contraction is then appended to the
end of the contraction list. This list can then be iterated over until all
intermediate contractions are complete.</p>
<p class="rubric">Examples</p>
<p>We can begin with a chain dot example. In this case, it is optimal to
contract the <code class="docutils literal notranslate"><span class="pre">b</span></code> and <code class="docutils literal notranslate"><span class="pre">c</span></code> tensors first as represented by the first
element of the path <code class="docutils literal notranslate"><span class="pre">(1,</span> <span class="pre">2)</span></code>. The resulting tensor is added to the end
of the contraction and the remaining contraction <code class="docutils literal notranslate"><span class="pre">(0,</span> <span class="pre">1)</span></code> is then
completed.</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">np</span><span class="o">.</span><span class="n">random</span><span class="o">.</span><span class="n">seed</span><span class="p">(</span><span class="mi">123</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">a</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">random</span><span class="o">.</span><span class="n">rand</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="mi">2</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">b</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">random</span><span class="o">.</span><span class="n">rand</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="mi">5</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">c</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">random</span><span class="o">.</span><span class="n">rand</span><span class="p">(</span><span class="mi">5</span><span class="p">,</span> <span class="mi">2</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">path_info</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">einsum_path</span><span class="p">(</span><span class="s1">&#39;ij,jk,kl-&gt;il&#39;</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">,</span> <span class="n">c</span><span class="p">,</span> <span class="n">optimize</span><span class="o">=</span><span class="s1">&#39;greedy&#39;</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="nb">print</span><span class="p">(</span><span class="n">path_info</span><span class="p">[</span><span class="mi">0</span><span class="p">])</span>
<span class="go">[&#39;einsum_path&#39;, (1, 2), (0, 1)]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="nb">print</span><span class="p">(</span><span class="n">path_info</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span>
<span class="go">  Complete contraction:  ij,jk,kl-&gt;il # may vary</span>
<span class="go">         Naive scaling:  4</span>
<span class="go">     Optimized scaling:  3</span>
<span class="go">      Naive FLOP count:  1.600e+02</span>
<span class="go">  Optimized FLOP count:  5.600e+01</span>
<span class="go">   Theoretical speedup:  2.857</span>
<span class="go">  Largest intermediate:  4.000e+00 elements</span>
<span class="go">-------------------------------------------------------------------------</span>
<span class="go">scaling                  current                                remaining</span>
<span class="go">-------------------------------------------------------------------------</span>
<span class="go">   3                   kl,jk-&gt;jl                                ij,jl-&gt;il</span>
<span class="go">   3                   jl,ij-&gt;il                                   il-&gt;il</span>
</pre></div>
</div>
<p>A more complex index transformation example.</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">I</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">random</span><span class="o">.</span><span class="n">rand</span><span class="p">(</span><span class="mi">10</span><span class="p">,</span> <span class="mi">10</span><span class="p">,</span> <span class="mi">10</span><span class="p">,</span> <span class="mi">10</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">C</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">random</span><span class="o">.</span><span class="n">rand</span><span class="p">(</span><span class="mi">10</span><span class="p">,</span> <span class="mi">10</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">path_info</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">einsum_path</span><span class="p">(</span><span class="s1">&#39;ea,fb,abcd,gc,hd-&gt;efgh&#39;</span><span class="p">,</span> <span class="n">C</span><span class="p">,</span> <span class="n">C</span><span class="p">,</span> <span class="n">I</span><span class="p">,</span> <span class="n">C</span><span class="p">,</span> <span class="n">C</span><span class="p">,</span>
<span class="gp">... </span>                           <span class="n">optimize</span><span class="o">=</span><span class="s1">&#39;greedy&#39;</span><span class="p">)</span>
</pre></div>
</div>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="nb">print</span><span class="p">(</span><span class="n">path_info</span><span class="p">[</span><span class="mi">0</span><span class="p">])</span>
<span class="go">[&#39;einsum_path&#39;, (0, 2), (0, 3), (0, 2), (0, 1)]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="nb">print</span><span class="p">(</span><span class="n">path_info</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span> 
<span class="go">  Complete contraction:  ea,fb,abcd,gc,hd-&gt;efgh # may vary</span>
<span class="go">         Naive scaling:  8</span>
<span class="go">     Optimized scaling:  5</span>
<span class="go">      Naive FLOP count:  8.000e+08</span>
<span class="go">  Optimized FLOP count:  8.000e+05</span>
<span class="go">   Theoretical speedup:  1000.000</span>
<span class="go">  Largest intermediate:  1.000e+04 elements</span>
<span class="go">--------------------------------------------------------------------------</span>
<span class="go">scaling                  current                                remaining</span>
<span class="go">--------------------------------------------------------------------------</span>
<span class="go">   5               abcd,ea-&gt;bcde                      fb,gc,hd,bcde-&gt;efgh</span>
<span class="go">   5               bcde,fb-&gt;cdef                         gc,hd,cdef-&gt;efgh</span>
<span class="go">   5               cdef,gc-&gt;defg                            hd,defg-&gt;efgh</span>
<span class="go">   5               defg,hd-&gt;efgh                               efgh-&gt;efgh</span>
</pre></div>
</div>
</dd></dl>

</div>


          </div>
        </div>
          </div>
        </div>
      </div>
    </div>

    <div class="container container-navbar-bottom">
      <div class="spc-navbar">
        
      </div>
    </div>
    <div class="container">
    <div class="footer">
    <div class="row-fluid">
    <ul class="inline pull-left">
      <li>
        &copy; Copyright 2008-2019, The SciPy community.
      </li>
      <li>
      Last updated on Feb 20, 2020.
      </li>
      <li>
      Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 2.4.2.
      </li>
    </ul>
    </div>
    </div>
    </div>
  </body>
</html>